package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @Classname E210
 * @Description leetcode 210. 课程表 II
 * @Date 2025/10/16 9:22
 * @Author 勾新杰
 */
public class E210 {

    /**
     * 拓扑排序，采用入度法
     *
     * @param numCourses    课程数量
     * @param prerequisites 课程依赖关系
     * @return 课程排序结果
     */
    public int[] findOrder1(int numCourses, int[][] prerequisites) {
        // 1. 填充图的数据结构
        List<Vertex> vertices = new ArrayList<>();
        // 1.1 添加顶点
        for (int i = 0; i < numCourses; i++) {
            vertices.add(new Vertex(i));
        }
        // 1.2 添加边
        for (int[] prerequisite : prerequisites) {
            vertices.get(prerequisite[1]).edges.add(new Edge(vertices.get(prerequisite[0])));
            vertices.get(prerequisite[0]).inDegree++;
        }
        // 2. 拓扑排序
        // 2.1 添加入度为0的顶点入队列
        LinkedList<Vertex> queue = new LinkedList<>();
        for (Vertex vertex : vertices) {
            if (vertex.inDegree == 0) {
                queue.offer(vertex);
            }
        }

        int[] result = new int[numCourses];
        int index = 0;

        // 2.2 遍历队列，取出入度为0的顶点，并遍历每个顶点的邻接顶点，将这些邻接顶点的入度减1
        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            for (Edge edge : vertex.edges) {
                edge.linked.inDegree--;
                if (edge.linked.inDegree == 0) {
                    queue.offer(edge.linked);
                }
            }
            result[index++] = vertex.index;
        }
        // 2.3 判断是否存在环
        if (index < numCourses) return new int[]{};
        return result;
    }

    /**
     * 拓扑排序，采用dfs
     *
     * @param numCourses    课程数量
     * @param prerequisites 课程依赖关系
     * @return 课程排序结果
     */
    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        // 1. 构建有向图
        List<Vertex> vertices = new ArrayList<>();
        ArrayList<Vertex> stack = new ArrayList<>();
        // 1.1 添加顶点
        for (int i = 0; i < numCourses; i++)
            vertices.add(new Vertex(i));
        // 1.2 添加边
        for (int[] prerequisite : prerequisites)
            vertices.get(prerequisite[1]).edges.add(new Edge(vertices.get(prerequisite[0])));
        // 2. 拓扑排序，遍历每个顶点尽心dfs
        try {
            for (Vertex vertex : vertices)
                dfsForTopicSort(vertex, stack);
        }
        // 3. 存在环则返回空数组
        catch (Exception e) {
            return new int[]{};
        }
        //int[] result = new int[numCourses];
        //int index = 0;
        //for (int i = numCourses - 1; i >= 0; i--) {
        //    result[index++] = stack.get(i).index;
        //}
        //return result;
        // 当前顶点入栈，入栈时机要是在归的时候，因为深度越深，达成条件越多，所以应当将那些入度为0的排在最前面，在这里就应当是栈顶
        Collections.reverse(stack);
        return stack.stream().mapToInt(vertex -> vertex.index).toArray();
    }

    /**
     * 拓扑排序，dfs
     *
     * @param vertex 当前顶点
     * @param stack  栈
     */
    private void dfsForTopicSort(Vertex vertex, ArrayList<Vertex> stack) {
        // 1. 当前顶点未访问
        if (vertex.status == 0) {
            // 2. 设置顶点状态为正在访问
            vertex.status = 1;
            for (Edge edge : vertex.edges) {
                dfsForTopicSort(edge.linked, stack);
            }
        }
        // 2. 当前顶点正在访问
        else if (vertex.status == 1) {
            throw new RuntimeException("存在环");
        }
        // 3. 当前顶点已访问
        else {
            return;
        }
        // 4. 当前顶点归的时候入栈并设置状态
        vertex.status = 2;
        stack.add(vertex);
    }

    /**
     * 顶点类
     */
    static class Vertex {

        /**
         * 顶点索引值，课程值
         */
        int index;

        /**
         * 顶点入度
         */
        int inDegree;

        /**
         * 顶点状态， 0-未访问，1-正在访问，2-已访问
         */
        int status;

        /**
         * 顶点邻接顶点
         */
        List<Edge> edges;

        /**
         * 顶点构造函数
         *
         * @param index 顶点索引值
         */
        Vertex(int index) {
            this.index = index;
            inDegree = 0;
            this.edges = new ArrayList<>();
        }
    }

    /**
     * 边类
     */
    static class Edge {

        /**
         * 边关联的顶点
         */
        Vertex linked;

        /**
         * 边构造函数
         *
         * @param linked 边关联的顶点
         */
        Edge(Vertex linked) {
            this.linked = linked;
        }
    }
}
